package fun.coding.datastructure;

import java.util.HashMap;
import java.util.Random;

/* insert, delete, contains, getRandom O(1) time. 
 * */
public class InsertDeleteContainsConstantTime {
    private static final int INIT_SIZE = 10;
    private HashMap<Object, Integer> map;
    private Object[] array;
    private int size;
    
    public InsertDeleteContainsConstantTime() {
        map = new HashMap<Object, Integer>();
        array = new Object[INIT_SIZE];
        size = 0;
    }
    
    public void insert(Object o) {
        int index = size;
        map.put(o, index);
        if (index < INIT_SIZE) {
            array[index] = o;
        } else {
            // auto scale
        }
        
        size++;
    }
    
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    
    public void delete(Object o) {
        if (!map.containsKey(o))
            return;
        
        int index = map.get(o);
        map.remove(o);
        array[index] = array[size - 1];
        map.put(array[size - 1], index);
        size--;
    } 
    
    public Object getRandom() {
        Random r = new Random();
        int index = r.nextInt(size);
        return array[index];
    }
    
    public static void main(String[] args) {
        InsertDeleteContainsConstantTime t = new InsertDeleteContainsConstantTime();
        t.insert(5);
        t.insert(10);
        t.insert(15);
        
        for (int i = 0; i < 5; ++i) {
            System.out.println("Before" + t.getRandom());
        }
        
        t.delete(10);
        for (int i = 0; i < 5; ++i) {
            System.out.println("After" + t.getRandom());
        }
    }
}
